1. Field of the Invention
The invention relates to a set-associative cache memory system and, more particularly, to a set-associative cache memory system in which each memory address is mapped to both a primary set and at least one other set.
2. Description of the Related Art
Most computer processing systems generally consist of several levels of memory, including at least one relatively small capacity high speed memory storage mechanism referred to as a cache memory. The cache memory may be located in either a section of the main memory or a separate memory storage device. There are several types of cache organization: direct-mapped, associative and set-associative. Direct-mapped caches are characterized by a one-to-one mapping from system address to cache address. Associative-mapped caches are characterized by mapping from any system address to any cache address. Set-associative caches are characterized by a one-to-many mapping from system address to a set address, but not to a particular line within the set. For example, in a four-way set-associative cache, the data corresponding to the system can be found in one of four lines in a set within the cache. There is a direct mapping from system address to set address. However, a tag (e.g., a subset of the upper system address bits) must be compared (e.g., by a comparator) with the tags for each of the four lines of the set to determine which line contains the data.
Some of the main determining factors in computer system processor performance are cache hit ratios. Specifically, it is desirable to obtain as high a cache hit ratio as possible subject to constraints such as minimal access latency and chip area. Cache misses can be categorized as conflict misses, capacity misses, and coherency misses. Conflict misses are an effect arising from set-associative cache designs, in which cache accesses from one process or thread by chance happen to map to the same set as other cache accesses from the same or other processes or threads, causing an excessive number of misses to that set. Typically, there are a number of “hot” sets, which dominate the overall number of cache misses. Here, a “hot” set is used as a generic term to refer to one of the sets in a set-associative cache for which there is an excessive number of conflict misses as compared to a typical set.
Various methods and systems for reducing conflict misses in set-associative cache memories are known. One method is to increase the associativity of the set-associative cache, and in fact there is a trend in recent computer system designs for increased associativity for the system caches. However, there are limits to which associativity can be increased in set-associative cache design. For example, in order to access the cache directory in a K-way associative cache, K tags are simultaneously read from K tag directories and simultaneously compared using K comparators to the tag of the address being accessed. As K increases, there is an increase in power requirements and power density. Additionally, the degree to which K can be increased is limited by wiring area, chip area, and timing constraints.
Another method, disclosed in U.S. Pat. No. 5,465,342, to Stephen J. Walsh, issued Nov. 7, 1995, for “Dynamically Adaptive Set Associativity for Cache Memories” (incorporated herein by reference), incorporates the use of “microcaches” that are dynamically assigned to sets that are identified as hot. There are a number of disadvantages to this and other conceptually similar approaches. Primarily, they require additional hardware complexity for counting misses for each set and for selecting those sets that have excessive miss counts as compared to typical sets.
Another method, disclosed in “The V-Way Cache: Demand Based Associativity via Global Replacement” by Qureshi, Thompson, and Pratt, University of Texas at Austin technical report TR-HPS-2004-003, October, 2004 (incorporated herein by reference), provides a system that reduces conflict misses by using a cache directory containing twice as many entries as the number of cache lines holding data. However, such a cache directory introduces extra chip area cost. A level of indirection is also introduced between the cache directory entries and cache lines via forward and reverse pointers, which may cause additional latency for every cache access.
Therefore, it would be advantageous to provide a set-associative cache memory with reduced conflict misses without increasing the associativity of the cache, without increasing the number of entries in the cache directory, without introducing levels of indirection between the cache directory and the cache, and without introducing additional latency for the most frequently accessed cache data. Specifically, it would be advantageous to provide a method that addresses the issue of conflict misses in set-associative cache memory by mapping a primary set address and at least one overflow (secondary) set address, by selecting a least recently used (LRU) line from within a set if a conflict miss occurs, by sending the selected line to an overflow set, and by replacing a line in the overflow set with the selected line, if the selected line is more recent.